package Simple;

import java.util.Arrays;
/** 
 * An array with n elements which is K most sorted，每个element的初始位置和它最终的排序后
 * 的位置的距离不超过常数K. 设计一个排序算法。It should be faster than O(n*lgn)。 
 *  
 *  
 * Given an array of n elements, where each element is at most k away from its target position, devise an 
 * algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in 
 * the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array. 
 *  
 * 一个已经排序好的很大的数组，现在给它划分成m段，每段长度不定，段长最长为k，然后段内打乱顺序，请设计一个算法
 * 对其进行重新排序”  
 *  
 * 两种解法： 
 * 1、插入排序，时间复杂度是O(n*k) 
 *    由于“K most sorted”，寻找位置时最多只会寻找k位，因此复杂度从最坏情况的O(n*n)下降到O(n*k), 但插入
 *    排序没有充分利用“K most sorted”这个条件 
 * 2、最小堆 
 *    如果认为堆的大小是k 
 *    这要看k most sorted怎么理解了 
 *    例如，如果对于{4, 3, 2, 1}认为k=3，那么堆的大小就应该是4。因为如果取3的话，第一次最小堆{2, 3, 4}排序后取出
 *    最小值2，第二次最小堆排序后取出最小值1，2排在1前面，显然不合理 
 *      
 *    最小堆的时间复杂度是O(k) + (n-k) * O(lgk)： 
 *    建堆：O(k)，k为堆的大小 
 *    堆排序：(n-k) * O(lgk) 
 *     
 */  
public class KSortedArray {
	public static void main(String[] args) {  
        int k = 3;  
        int[] array = {2, 6, 3, 12, 56, 8};  
        insertSort(array);  
        minHeapSort(array, k);  
    }  
      
    public static void insertSort(int[] arrayToSort) {  
  
        //...略去输入合法性检查  
          
        //复制数组，不影响原数组  
        int len = arrayToSort.length;  
        int[] array = new int[len];  
        System.arraycopy(arrayToSort, 0, array, 0, len);  
          
        for (int i = 1; i < len; i++) {  
            int itemToInsert = array[i];  
            while(i > 0 && itemToInsert < array[i - 1]) {  
                array[i] = array[i - 1];  
                i--;  
            }  
            array[i] = itemToInsert;  
        }  
          
        System.out.println(Arrays.toString(array));  
    }  
  
    public static void minHeapSort(int[] arrayToSort, int k) {  
          
        int len = arrayToSort.length;  
        int[] array = new int[len];  
        System.arraycopy(arrayToSort, 0, array, 0, len);  
          
        int[] sortedArray = new int[len];  
        int[] heapValues = new int[k + 1];  
        System.arraycopy(array, 0, heapValues, 0, k + 1);  
        MinHeap heap = new MinHeap(heapValues);  
          
        //将剩下的元素陆续推入堆里，并“吐”出最小值  
        int j = 0;  
        for (int i = k + 1; i < len; i++) {  
            sortedArray[j++] = heap.getRootValue();  
            heap.replaceRootValueWith(array[i]);  
            heap.reheap();  
        }  
          
        //没有更多元素进入了，此时剩下k个元素，堆不断收缩，直至为0  
        //事实上这个while循环可以并入上面的for循环  
        while (j < len) {  
            sortedArray[j++] = heap.getRootValue();   
            heap.minimize();  
        }  
          
        System.out.println(Arrays.toString(sortedArray));  
    }  
}  
  
  
/** 
 * 最小堆，只将本次排序中调用到的方法声明为public 
 */  
class MinHeap {  
      
    private int[] values;  
    private int lastIndex;  
      
    public MinHeap(int[] values) {  
        init(values);  
    }  
      
    public void reheap() {  
        reheapCore(0, values.length - 1);  
    }  
      
    public int getRootValue() {  
        return values[0];  
    }  
      
    public void replaceRootValueWith(int newRootValue) {  
        values[0] = newRootValue;  
    }  
      
    public void minimize() {  
        if (lastIndex > 0) {  
            this.replaceRootValueWith(values[lastIndex]);  
            lastIndex--;  
            this.reheapCore(0, lastIndex);  
        }  
    }  
      
    private void init(int[] values) {  
        int size = values.length;  
        this.lastIndex = size - 1;  
        this.values = new int[size];  
        System.arraycopy(values, 0, this.values, 0, size);  
        int lastIndex = size - 1;  
        int lastRootIndex = getRootIndex(lastIndex);  
        for (int rootIndex = lastRootIndex; rootIndex >= 0; rootIndex--) {  
            reheapCore(rootIndex, lastIndex);  
        }  
    }  
      
    private void reheapCore(int rootIndex, int lastIndex) {  
        if (!(isValidIndex(rootIndex) && isValidIndex(lastIndex))) {  
            System.out.println("invalid parameters");  
            return;  
        }  
        int orphan = values[rootIndex];  
        int leftIndex = getLeftIndex(rootIndex);  
        boolean done = false;  
        while (!done && leftIndex <= lastIndex) {  
            int rightIndex = getRightIndex(rootIndex);  
            int smallerIndex = leftIndex;  
            if (rightIndex <= lastIndex && values[rightIndex] < values[leftIndex]) {  
                smallerIndex = rightIndex;  
            }   
            if (values[smallerIndex] < values[rootIndex]) {  
                swap(values, smallerIndex, rootIndex);  
                rootIndex = smallerIndex;  
                leftIndex = getLeftIndex(rootIndex);  
            } else {  
                done = true;  
            }  
        }  
        values[rootIndex] = orphan;  
        //System.out.println(Arrays.toString(values));  
    }  
      
    private int getLeftIndex(int rootIndex) {  
        return rootIndex * 2 + 1;  
    }  
      
    private int getRightIndex(int rootIndex) {  
        return rootIndex * 2 + 2;  
    }  
      
    private int getRootIndex(int childIndex) {  
        return (childIndex - 1) / 2;  
    }  
      
    private boolean isValidIndex(int index) {  
        return index >=0 && index < values.length;  
    }  
      
    private void swap(int[] array, int i, int j) {  
        int tmp = array[i];  
        array[i] = array[j];  
        array[j] = tmp;  
    }  

}
